1. Field of the Invention
This invention relates to the field of packet routing and more particularly relates to methods and apparatus for managing traffic flow in routers and switches.
2. Description of the Related Art
Routers in a network receive packets from different data streams. Each data stream is classified based on various characteristics of the data (e.g., type of data, source address, destination address, protocol used or the like). Such a data stream can be referred to as ‘flow’. During traffic congestion in the network, some flows dynamically adapt to available bandwidth and control the data rate accordingly. The flows that adapt to available bandwidth are referred to as Well Behaved Flows (“WBF”). When faced with packet drops (i.e., packets discarded deliberately by a downstream device due to congestion at that device), these WBFs reduce their flow rates and send fewer packets per unit of time. WBFs, such as conventional TCP flows, implement a control loop to adjust transmission rate to the rate available through the bottleneck link on the path. By adjusting the rate, WBFs have no packets queued at routers through which the WBFs transit much of the time.
Other flows, however, do not dynamically adapt to available bandwidth. Non-adaptive flows are referred to as Non-adaptive Aggressive Flows (“NAF”). NAFs do not throttle back the flow of packets to the router when they experience packet drops. This may be because either the NAFs do not recognize the congestion (e.g., due to protocol incompatibilities), or because the NAFs actually are trying to capture more router bandwidth during the congestion. A flow that sends packets at an excessive rate can deplete buffer and queue resources causing packet delay and drop by WBFs.
Buffer/queue management mechanisms can reduce the amount of buffering used by aggressive flows. However, it is very difficult to reduce buffer consumption to zero without denying the flow altogether. It is often difficult to determine whether the flow is truly non-adaptive or simply slow to adapt because of roundtrip packet delay in the network. Consequently, NAFs are often allowed a minimal amount of buffering. Unfortunately, even minimum amount of buffering can cause persistent queues and buffer consumption at a port, causing extra delay for WBFs.
For example, when a router limits the buffering for NAF to two packets and 100 NAFs go through a port then assuming FIFO queuing, each WBF can be delayed by 200 packet times. WBFs need to have at least as many packets queued as the NAFs on that port to get a comparable data rate through the router. WBFs need more queue space because of their back-off reaction to packet drop and the congestion. Consequently, with 100 WBFs and 100 NAFs through a given port, a new packet can expect to experience a queuing delay of 400 packet times or more.
Several flow regulation schemes are known in the art. Broadly classified, these schemes fall into two types: queue-based and buffer-based. In queue-based schemes, incoming flows are classified according to their actual priority, as determined by the receiving router, and assigned accordingly to output queues within the router. These schemes are generally referred to as “class-based queuing” (CBQ) techniques. High priority flows, such as time-sensitive voice traffic, are placed in a queue that is read out more often. Low priority flows, such as file transfer protocol (FTP) or hypertext transfer protocol (HTTP) flows, are placed in queues that are read out of the router at a slower rate. Per flow queuing is expensive in memory and processing is complex to implement, particularly in high-speed switches.
In buffer-based management scheme, the router limits the amount of packet buffers assigned to a particular input flow. Such limits on the number of packets buffered per flow can be either static or dynamic. In the static or strict limit scheme, a set maximum number of buffers is available for each flow. Any packets received after those buffers are full, the router discards the packets. The static limits are set by the system administrator for each type of flow. However, buffer-based scheme has the obvious drawback of high overhead associated with setting up a gating mechanism for each flow and administrative oversight. Additionally, buffer-based scheme lacks long-term flexibility to adapt to the wide variety and constantly changing mix of flow types.
Alternately, flows can be individually policed to the available rate. A packet can be dropped if the flow is over its allotted rate. However, this approach would require a large number of policers, and rapid modification of the policer rate as the available bandwidth and number of flows at a port changes. What is needed is a dynamic method of flow control that is able to rapidly adapt to flows and prevent NAFs from unfairly seizing bandwidth.